<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>插入排序</title>
</head>
<body>
  <script>
    /** 插入排序
     * 
     * 工作原理：类似于整理扑克牌，在未排序区间取一个元素，与左侧已排序区间逐一比较大小，并将该元素插入到对应位置
     * 
     * 步骤：
     * 1.初始状态下，第一个元素已经完成排序
     * 2.选取数组的第 2 个元素，从右向左遍历已排序区间，找到正确位置，插入。数组前 2 个元素完成排序
     * 以此类推
     * 3.选取数组的第 3 个元素，从右向左遍历已排序区间，找到正确位置，插入。数组前 3 个元素完成排序
     * 4.选取数组的最后一个元素，从右向左遍历已排序区间，找到正确位置，插入。数组完成排序
     * 
     * 时间复杂度：O(n2)   空间复杂度：O(1)
     * 
     * 稳定排序，推荐使用
    */

    const data = [5,4,6,7,3,8,2,9,1,0,10,3]

    function insertSort(arrs) {
      const arr = [...arrs]
      for (let i = 1; i < arr.length; i++) {
        const tempi = arr[i];  // tempi 未排序区间的第一个元素
        // 从右向左遍历已排序区间，i-1 为已排序区间的最大索引
        for (let j = i-1; j >= 0; j--) { 
          // 遍历已排序区间的元素，arr[j] 已排序区间的元素
          if(tempi < arr[j]) { // 1 2 3(2)    5(3)
            arr[j+1] = arr[j] // arr[j] 进行右移一个位置
            arr[j] = tempi //  arr[j] 赋值 tempi
          } else {
            arr[j+1] = tempi // 将 tempi 插入到索引为 j 的位置
            break;
          }
        }

        // 第二种写法
        // let j = i - 1; // 已排序区间的最大索引
        // while (j >= 0 && tempi < arr[j]) {
        //   arr[j+1] = arr[j] // arr[j] 右移一个单位
        //   j-- // 继续循环
        // }
        // arr[j+1] = tempi // arr[j+1] 处赋值 tempi
      }
      return arr
    }

    const result = insertSort(data)
    document.write('插入排序：', result)
  </script>
</body>
</html>